Search results for "Mixed Chinese postman problem"

showing 2 items of 2 documents

A comparison of two different formulations for Arc Routing Problems on Mixed graphs

2006

[EN] Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.

Arc routingGeneral Computer ScienceLinear programmingMixed Chinese postman problemMixed graphMixed rural postman problemManagement Science and Operations ResearchRoute inspection problemTree traversalModeling and SimulationEnhanced Data Rates for GSM EvolutionRouting (electronic design automation)Mixed general routing problemMATEMATICA APLICADAAlgorithmArc routingMathematicsVariable (mathematics)
researchProduct

The mixed general routing polyhedron

2003

[EN] In Arc Routing Problems, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the…

Discrete mathematicsGeneral MathematicsArc RoutingMixed graphFacetsPolyhedral combinatoricsRural Postman Problemlaw.inventionGeneral Routing ProblemCombinatoricsTree traversalMixed Chinese Postman ProblemlawroutingGraph traversalGraph (abstract data type)Destination-Sequenced Distance Vector routingMATEMATICA APLICADACircle graphArc routingSoftwareMathematicsofComputing_DISCRETEMATHEMATICSMathematicsPolyhedral graph
researchProduct